package com.fw.leetcode.doublepointer;

import com.fw.leetcode.LeetCode;

import java.util.Arrays;

/**
 * 189. Rotate Array
 *
 * Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.
 *
 * Example 1:
 *  Input: nums = [1,2,3,4,5,6,7], k = 3
 *  Output: [5,6,7,1,2,3,4]
 *  Explanation:
 *    rotate 1 steps to the right: [7,1,2,3,4,5,6]
 *    rotate 2 steps to the right: [6,7,1,2,3,4,5]
 *    rotate 3 steps to the right: [5,6,7,1,2,3,4]
 *
 * Example 2:
 *  Input: nums = [-1,-100,3,99], k = 2
 *  Output: [3,99,-1,-100]
 *  Explanation:
 *    rotate 1 steps to the right: [99,-1,-100,3]
 *    rotate 2 steps to the right: [3,99,-1,-100]
 *
 * Constraints:
 *  1 <= nums.length <= 10^5
 *  -2^31 <= nums[i] <= 2^31 - 1
 *  0 <= k <= 10^5
 *
 * Follow up:
 *  Try to come up with as many solutions as you can. There are at least three different ways to solve this problem.
 *  Could you do it in-place with O(1) extra space?
 */
public class Num_0189 implements LeetCode {
    private interface Solution {
        void rotate(int[] nums, int k);

        default void assertEquals(int[] nums, int k, int[] expected) {
            int[] oldNums = new int[nums.length];
            System.arraycopy(nums, 0, oldNums, 0, nums.length);
            rotate(nums, k);
            if (!Arrays.equals(nums, expected)) {
                rotate(oldNums, k);
            }
        }
    }

    private static class MyReverseSolution implements Solution {

        @Override
        public void rotate(int[] nums, int k) { // 分段翻转：时O(n) 空O(1)
            /*
             * 轮转数组
             * 数组分步翻转
             * nums = [1,2,3,4,5,6,| 7], k = 1 => [7 |,1,2,3,4,5,6]
             * => 1. [7,6,5,4,3,2,1]
             * => 2. [7,1,2,3,4,5,6]
             * nums = [1,2,3,4,| 5,6,7], k = 3 => [5,6,7 |,1,2,3,4]
             * => 1. [7,6,5,4,3,2,1]
             * => 2. [5,6,7,| 1,2,3,4]
             * nums = [1,2,3,| 4,5,6,7], k = 4 => [4,5,6,7 |,1,2,3]
             * => 1. [7,6,5,4,3,2,1]
             * => 2. [4,5,6,7,| 1,2,3]
             *
             * 特例：
             * nums = [-1], k = 2 => [-1]
             */
            k = k % nums.length; // 避免多遍环形移动，降到一遍，如：n=2,k=18
            reverse(nums, 0, nums.length-1); // 整个翻转 [0,n-1]
            reverse(nums, 0, k-1); // 翻转 [0,k-1]
            reverse(nums, k, nums.length-1); // 翻转 [k,n-1]
        }

        private void reverse(int[] nums, int left, int right) {
            while (left < right) {
                int tmp = nums[left];
                nums[left] = nums[right];
                nums[right] = tmp;
                left++;
                right--;
            }
        }
    }

    private static class MyCycleSolution implements Solution {

        @Override
        public void rotate(int[] nums, int k) { // 环形单指针：时O(n) 空O(1)
            /*
             * 轮转数组
             * 环形公式：nums[i] → nums[(i+k)%n]
             * nums = [1,2,3,4,5,6,7], k = 1 => [7,1,2,3,4,5,6]
             * nums = [1,2,3,4,5,6,7], k = 3 => [5,6,7,1,2,3,4]
             * nums = [1,2,3,4,5,6,7], k = 4 => [4,5,6,7,1,2,3]
             * nums = [1,2,3,4], k = 2 => [3,4,1,2]  # 环形死循环 1|3 2|4
             */
            int moveTimes = nums.length; // 共需移动 n 次
            int idx = 0; // 初始位置
            int startIdx = idx; // 记录环形移动起始点，避免无限循环
            while (moveTimes > 0) {
                idx = (idx + k) % nums.length; // 计算目标移动位置
                int tmp = nums[startIdx]; // 临时存储
                nums[startIdx] = nums[idx]; // startIdx 位置可作为环形中的元素寄存点，直到环形的最后一次被填充正确值
                nums[idx] = tmp; // 写入目标位置
                moveTimes--;
                if (idx == startIdx) { // 环形轮回到起点，后移环形起点
                    startIdx++;
                    idx = startIdx;
                }
            }
        }
    }

    private static class MySolution implements Solution {

        @Override
        public void rotate(int[] nums, int k) { // 位置映射额外数组：时O(n) 空O(n)
            /*
             * 轮转数组
             * 环形公式：nums[i] → nums[(i+k)%n]
             * nums = [1,2,3,4,5,6,7], k = 1 => [7,1,2,3,4,5,6]
             * nums = [1,2,3,4,5,6,7], k = 3 => [5,6,7,1,2,3,4]
             * nums = [1,2,3,4,5,6,7], k = 4 => [4,5,6,7,1,2,3]
             */
            int[] result = new int[nums.length];
            for (int i = 0; i < nums.length; i++) {
                result[(i+k)%nums.length] = nums[i];
            }
            System.arraycopy(result, 0, nums, 0, nums.length);
        }
    }

    public static void main(String[] args) {
        Solution solution = new MyReverseSolution();
        solution.assertEquals(new int[]{1,2,3,4,5,6,7}, 3, new int[]{5,6,7,1,2,3,4});
        solution.assertEquals(new int[]{-1,-100,3,99}, 2, new int[]{3,99,-1,-100});
        solution.assertEquals(new int[]{-1}, 2, new int[]{-1});
    }
}
